Hilbert Projection Theorem

Let HH be a Hilbert space ( inner product space that is complete with respect to the norm induced by the inner product) and MM be a finite dimensioal subspace of HH. Then for any x∈Hx \in H, there exists a unique y∈My \in M such that

min⁡m∈M∥x−m∥\min_{m \in M} \|x-m\|

has a unique solution yy. In other words "we can find a unique point in MM that is closest to xx". If m∗m^* is the closest point to xx in MM, then x−m∗⊥Mx-m^* \perp M.

Proof: See lecture notes.

Remark: The proof stated that m∗=x1m^* = x_1 is the closest point to MM. It can also be interpreted as the best approximation of xx choosen from the vectors in MM. The x2x_2 term is the error in the approximation.

Example: Let V=R2V=\mathbb{R}^2 and M=span{[1,1]T}M = \text{span}\{[1,1]^T\}. Find the best approximation of x=[4,7]Tx=[4,7]^T in MM.

Solution: We need to find m∗m^* such that m∗=α[11]m^* = \alpha \begin{bmatrix} 1 \\ 1 \end{bmatrix} and ∥x−m∗∥\|x-m^*\| is minimum.

(x−m∗)⊥M  ⟹  <x−m∗,m>=0∀m∈M(x-m^*) \perp M \implies <x-m^*, m> = 0 \quad \forall m \in M
<x−m∗,[11]>=0<x-m^*, \begin{bmatrix} 1 \\ 1 \end{bmatrix}> = 0
Replace x and m∗ with their values.\text{Replace $x$ and $m^*$ with their values.}
<[4−α7−α],[11]>=0<\begin{bmatrix} 4-\alpha \\ 7-\alpha \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \end{bmatrix}> = 0
Recall that <x,y>=xTy.\text{Recall that $1lt;x,y> = x^Ty$.}
4−α+7−α=04-\alpha + 7-\alpha = 0
α=112\alpha = \frac{11}{2}
m∗=112[11]m^* = \frac{11}{2} \begin{bmatrix} 1 \\ 1 \end{bmatrix}

Example: Let x∈Vx \in V and M=span{v1,v2}M = \text{span}\{v_1, v_2\}. Find the best approximation of xx in MM.

Solution: We need to find m∗m^* such that m∗=α1v1+α2v2m^* = \alpha_1 v_1 + \alpha_2 v_2 that is in the span of MM and ∥x−m∗∥\|x-m^*\| is minimum.

(x−m∗)⊥M  ⟹  (x−m∗)⊥both v1 and v2(x-m^*) \perp M \implies (x-m^*) \perp \text{both } v_1 \text{ and }v_2
<x−α1v1−α2v2,v1>=<x,v1>−α1<v1,v1>−α2<v2,v1>=0<x-\alpha_1 v_1 - \alpha_2 v_2, v_1> = <x, v_1> - \alpha_1 <v_1, v_1> - \alpha_2 <v_2, v_1> = 0
<x−α1v1−α2v2,v2>=<x,v2>−α1<v1,v2>−α2<v2,v2>=0<x-\alpha_1 v_1 - \alpha_2 v_2, v_2> = <x, v_2> - \alpha_1 <v_1, v_2> - \alpha_2 <v_2, v_2> = 0
[<v1,v1><v2,v1><v1,v2><v2,v2>][α1α2]=[<x,v1><x,v2>]\begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
[α1α2]=[<v1,v1><v2,v1><v1,v2><v2,v2>]−1[<x,v1><x,v2>]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix}^{-1} \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
m∗=α1v1+α2v2m^* = \alpha_1 v_1 + \alpha_2 v_2

Example: Let V=R3V = \mathbb{R}^3 and M=span{[1,1,1]T,[1,0,1]T}M = \text{span}\{[1,1,1]^T, [1,0,1]^T\}. Find the best approximation of x=[4,7,2]Tx=[4,7,2]^T in MM.

Solution: We need to find m∗m^* such that m∗=α1[111]+α2[101]m^* = \alpha_1 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} + \alpha_2 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} that is in the span of MM and ∥x−m∗∥\|x-m^*\| is minimum.

(x−m∗)⊥M  ⟹  (x−m∗)⊥both v1 and v2(x-m^*) \perp M \implies (x-m^*) \perp \text{both } v_1 \text{ and }v_2
[<v1,v1><v2,v1><v1,v2><v2,v2>][α1α2]=[<x,v1><x,v2>]\begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
Recall that <x,y>=xTy.\text{Recall that $1lt;x,y> = x^Ty$.}
[3222][α1α2]=[136]\begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[3222]−1[136]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix}^{-1} \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[1−1−13/2][136]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ -1 & 3/2 \end{bmatrix} \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[7−4]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 7 \\ -4 \end{bmatrix}
m∗=α1v1+α2v2=7[111]−4[101]=[373]m^* = \alpha_1 v_1 + \alpha_2 v_2 = 7 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - 4 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 3 \\ 7 \\ 3 \end{bmatrix}

Example: Let HH be the space of square integrable functions on [−π,π][-\pi , \pi ] with inner product <f,g>=∫−ππf(t)g(t)ˉdt<f,g> = \int_{-\pi}^{\pi} f(t)\bar{g(t)}dt. Let MM be the subspace of HH, M=span{ejkt/2π}M = \text{span}\{e^{jkt}/\sqrt{2\pi}\}, k from −N to Nk \text{ from } -N \text{ to } N. Note that dimension of MM is 2N+12N+1.

<fn,fm>=∫−ππejnt2πe−jmt2πdt=12π∫−ππej(n−m)tdt<f_n, f_m> = \int_{-\pi}^{\pi} \frac{e^{jnt}}{\sqrt{2\pi}} \frac{e^{-jmt}}{\sqrt{2\pi}} dt = \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt
If n≠m, then 12π∫−ππej(n−m)tdt=12πej(n−m)tj(n−m)∣−ππ=0\text{If $n \neq m$, then } \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt = \frac{1}{2\pi} \frac{e^{j(n-m)t}}{j(n-m)} \Big|_{-\pi}^{\pi} = 0
If n=m, then 12π∫−ππej(n−m)tdt=12π∫−ππ1dt=1\text{If $n = m$, then } \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt = \frac{1}{2\pi} \int_{-\pi}^{\pi} 1 dt = 1
Therefore, <fn,fm>={1if n=m0if n≠m\text{Therefore, } <f_n, f_m> = \begin{cases} 1 & \text{if $n = m$} \\ 0 & \text{if $n \neq m$} \end{cases}

Now, let g∈Hg \in H be an arbitrary function. Then g=g1+g2g = g_1 + g_2 where g1∈Mg_1 \in M and g2∈M⊥g_2 \in M^{\perp}. We need to find g1g_1 such that ∥g−g1∥\|g-g_1\| is minimum.

g1=∑k=−NNαkejkt2π where αk=<g,fk>=∫−ππg(t)e−jkt2πdt g_1 = \sum_{k=-N}^{N} \alpha_k \frac{e^{jkt}}{\sqrt{2\pi}} \text{ where } \alpha_k = <g, f_k> = \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} dt
αk=∫−ππg(t)e−jkt2πdt \alpha_k = \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} dt
g1=∑k=−NN∫−ππg(t)e−jkt2πejkt2πdt=∑k=−NN∫−ππg(t)12πdt=∫−ππg(t)dt g_1 = \sum_{k=-N}^{N} \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} \frac{e^{jkt}}{\sqrt{2\pi}} dt = \sum_{k=-N}^{N} \int_{-\pi}^{\pi} g(t) \frac{1}{2\pi} dt = \int_{-\pi}^{\pi} g(t) dt

Example: Find the orthagonal projection of the vector [100]\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} onto the subspace M=span{[111],[1−11]}M = \text{span}\{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix}\}.

Solution: We know that the projection matrix is P=B(BTB)−1BTP = B(B^TB)^{-1}B^T where BB is the matrix whose columns are the basis vectors of MM. Therefore,

B=[111−111]B = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix}
BTB=[3113]B^TB = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}
P=[111−111][3113]−1[1111−11]P = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \end{bmatrix}
P=[111−111][3/8−1/8−1/83/8][1111−11]P = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3/8 & -1/8 \\ -1/8 & 3/8 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \end{bmatrix}
P=[1/201/20101/201/2]P = \begin{bmatrix} 1/2 & 0 & 1/2 \\ 0 & 1 & 0 \\ 1/2 & 0 & 1/2 \end{bmatrix}
P[100]=[1/201/2]P \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1/2 \\ 0 \\ 1/2 \end{bmatrix}

Solution of Linear Equations

Consider the linear equation expressed as

Ax=b where A∈Cm×n,x∈Cn,b∈CmAx = b \text{ where } A \in \mathbb{C}^{m \times n}, x \in \mathbb{C}^n, b \in \mathbb{C}^m

If m=nm = n, then the equation has a unique solution. If m<nm < n, then the equation has infinitely many solutions. If m>nm > n, then the equation has no solution.

Example: Let A=[1111]A = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} and b=[2.21.92.11.8]b = \begin{bmatrix} 2.2 \\ 1.9 \\ 2.1 \\ 1.8 \end{bmatrix}. Find xx such that Ax=bAx = b.

Solution:

b∈?range(A) b \in^{?} \text{range}(A)
range(A)=span{[1,1,1,1]T}\text{range}(A) = \text{span}\{[1,1,1,1]^T\}
span{[1,1,1,1]T}={[a,a,a,a]T∣a∈R}\text{span}\{[1,1,1,1]^T\} = \{[a,a,a,a]^T \mid a \in \mathbb{R}\}
b∉range(A)b \notin \text{range}(A)

Therefore, there is no exact solution. We need to find the best approximation of bb in range(A)\text{range}(A).

Lets call this best approximation b∗b^*. Then, b∗=α[1111]b^* = \alpha \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} and ∥Ax−b∗∥2\|Ax-b^*\|^2 is minimum.

B=[1111]B = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}
P=[1111][4]−1[1111]P = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 4 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}
Pb=[1111][4]−1[1111][2.21.92.11.8]Pb = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 4 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2.2 \\ 1.9 \\ 2.1 \\ 1.8 \end{bmatrix}
Pb=b∗=[2.02.02.02.0]Pb = b^* = \begin{bmatrix} 2.0 \\ 2.0 \\ 2.0 \\ 2.0 \end{bmatrix}

Example: Let A=[21212121]A = \begin{bmatrix} 2 & 1 \\ 2 & 1 \\ 2 & 1 \\ 2 & 1 \end{bmatrix} and b=[l1l2l3l4]b = \begin{bmatrix} l_1 \\ l_2 \\ l_3 \\ l_4 \end{bmatrix}. Find xx such that Ax=bAx = b.

Solution: Now, the rows of AA are linearly dependent. Therefore, AA is not full column rank. Therefore, there is no exact solution. We need to find the best approximation of bb in range(A)\text{range}(A).

b∗=[lˉlˉlˉlˉ] where lˉ=l1+l2+l3+l44b^* = \begin{bmatrix} \bar l \\ \bar l \\ \bar l \\ \bar l \end{bmatrix} \text{ where } \bar l = \frac{l_1+l_2+l_3+l_4}{4}
[21212121][x1x2]=[lˉlˉlˉlˉ]\begin{bmatrix} 2 & 1 \\ 2 & 1 \\ 2 & 1 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix}\bar l \\ \bar l \\ \bar l \\ \bar l \end{bmatrix}
[x1x2]=[lˉ−lˉ] is any solution, more examples [1−1],[2−3],[3−5],…\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} \text{ is any solution, more examples } \begin{bmatrix} 1 \\ -1 \end{bmatrix}, \begin{bmatrix} 2 \\ -3 \end{bmatrix}, \begin{bmatrix} 3 \\ -5 \end{bmatrix}, \ldots
A minimum norm solution is can be found by minimizing the norm of x.\text{A minimum norm solution is can be found by minimizing the norm of $x$.}
 For that, we can project any solution onto the null space perpendicular to A.\text{ For that, we can project any solution onto the null space perpendicular to $A$.}
x1=ProjN(A)⊥[lˉ−lˉ]x_1 = \text{Proj}_{N(A)^{\perp}} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}
Corollary: N(A)⊥=range(A∗)\text{Corollary: } N(A)^{\perp} = \text{range}(A^*)
A∗=[22221111]A^* = \begin{bmatrix} 2 & 2 & 2 & 2 \\ 1 & 1 & 1 & 1 \end{bmatrix}
range(A∗)=span{[21]}\text{range}(A^*) = \text{span}\bigg \{\begin{bmatrix} 2 \\ 1 \end{bmatrix}\bigg\}
ProjN(A)⊥[lˉ−lˉ]=Projrange(A∗)[lˉ−lˉ]\text{Proj}_{N(A)^{\perp}} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}
Projrange(A∗)[lˉ−lˉ]=<[lˉ−lˉ],[21]><[21],[21]>[21]\text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \frac{<\begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}, \begin{bmatrix} 2 \\ 1 \end{bmatrix}>}{<\begin{bmatrix} 2 \\ 1 \end{bmatrix}, \begin{bmatrix} 2 \\ 1 \end{bmatrix}>} \begin{bmatrix} 2 \\ 1 \end{bmatrix}
Projrange(A∗)[lˉ−lˉ]=lˉ5[21]\text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \frac{\bar l}{5} \begin{bmatrix} 2 \\ 1 \end{bmatrix}
 Or in projection matrix form, Q=[21] then, P=Q(Q∗Q)−1Q∗\text{ Or in projection matrix form, } Q = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \text{ then, } P = Q(Q^*Q)^{-1}Q^*
P=[21]15[21]=[4/52/52/51/5]P = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \frac{1}{5} \begin{bmatrix} 2 & 1 \end{bmatrix} = \begin{bmatrix} 4/5 & 2/5 \\ 2/5 & 1/5 \end{bmatrix}
x1=Px=[4/52/52/51/5][lˉ−lˉ]=[4/5lˉ−2/5lˉ2/5lˉ−1/5lˉ]=[2/5lˉ1/5lˉ]=lˉ/5[21]x_1 = Px = \begin{bmatrix} 4/5 & 2/5 \\ 2/5 & 1/5 \end{bmatrix} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \begin{bmatrix} 4/5 \bar l - 2/5 \bar l \\ 2/5 \bar l - 1/5 \bar l \end{bmatrix} = \begin{bmatrix} 2/5 \bar l \\ 1/5 \bar l \end{bmatrix} = \bar l/ 5 \begin{bmatrix} 2 \\ 1 \end{bmatrix}

Special Cases of Ax=bAx = b

1.1 Columns of AA are linearly independent

If the columns of AA are linearly independent, then AA is full rank and ATAA^TA is invertible. Therefore, x=(ATA)−1ATbx = (A^TA)^{-1}A^Tb is the unique solution.

AA is full column rank with AA is m×nm \times n and m≥nm \geq n if and only if N(A)={0}N(A) = \{0\}. (Tall matrix)

If b∈range(A)b \in \text{range}(A), then the solution exists and is unique. If b∉R(A)b \notin \text{R}(A), then the solution does not exist.

Ax=ProjR(A)bAx = \text{Proj}_{\text{R}(A)}b is the best approximation of bb in R(A)\text{R}(A).

P=A(ATA)−1ATP = A(A^TA)^{-1}A^T is the projection matrix onto R(A)\text{R}(A).

Ax=A(ATA)−1ATbAx = A(A^TA)^{-1}A^Tb is the best approximation of bb in R(A)\text{R}(A).

Ax−A(ATA)−1ATb=0Ax - A(A^TA)^{-1}A^Tb = 0 since the projection of bb onto R(A)\text{R}(A).

A(x−(ATA)−1ATb)=0A(x - (A^TA)^{-1}A^Tb) = 0

x−(ATA)−1ATb∈N(A)x - (A^TA)^{-1}A^Tb \in N(A) and the null space contains only the zero vector.

x=(ATA)−1ATbx = (A^TA)^{-1}A^Tb is the unique solution.

1.2 Columns of AA are linearly dependent

If the columns of AA are linearly dependent, then AA is not full rank and ATAA^TA is not invertible. Therefore, x=(ATA)−1ATbx = (A^TA)^{-1}A^Tb is not the unique solution.

2.1 Rows of AA are linearly independent

If the rows of AA are linearly independent, then AA is full row rank and AATAA^T is invertible. Therefore, x=AT(AAT)−1bx = A^T(AA^T)^{-1}b is the unique solution.

AA is full row rank with AA is m×nm \times n and m≤nm \leq n if and only if N(AT)={0}N(A^T) = \{0\}. (Wide matrix)

If b∈range(A)b \in \text{range}(A), then the solution exists and is unique. If b∉R(A)b \notin \text{R}(A), then the solution does not exist.

dim(R(A))=dim(R(AT))=rank(A)=rank(AT)  ⟹  b∈R(A)\text{dim}(\text{R}(A)) = \text{dim}(\text{R}(A^T)) = \text{rank}(A) = \text{rank}(A^T) \implies b \in \text{R}(A)

For a minimum norm solution, we need to project bb onto the null space perpendicular to AA.

x=ProjN(A)⊥b=ProjR(A∗)bx = \text{Proj}_{N(A)^{\perp}}b = \text{Proj}_{\text{R}(A^*)}b

P=A∗(AA∗)−1A=A∗(A∗A)−1AP = A^*(AA^*)^{-1}A = A^*(A^*A)^{-1}A

Px=A∗(AA∗)−1Ax=A∗(AA∗)−1bPx = A^*(AA^*)^{-1}Ax = A^*(AA^*)^{-1}b

2.2 Rows of AA are linearly dependent

If the rows of AA are linearly dependent, then AA is not full row rank and AATAA^T is not invertible. Therefore, x=AT(AAT)−1bx = A^T(AA^T)^{-1}b is not the unique solution.

3.1 AA is square and invertible

If AA is square and invertible, then x=A−1bx = A^{-1}b is the unique solution.

Example: Let A=[111123321]A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 3 & 2 & 1 \end{bmatrix} and b=[12−1]b = \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix}. Find xx such that Ax=bAx = b.

Solution:

First, we need to check if b∈range(A)b \in \text{range}(A). Since AA has linearly dependent columns

range(A)=span{[113],[131]}\text{range}(A) = \text{span}\bigg\{\begin{bmatrix} 1 \\ 1 \\ 3 \end{bmatrix}, \begin{bmatrix} 1 \\ 3 \\ 1 \end{bmatrix}\bigg\}
dim(range(A))=rank(A)=2\text{dim}(\text{range}(A)) = \text{rank}(A) = 2
dim(N(A))=n−rank(A)=3−2=1\text{dim}(N(A)) = n - \text{rank}(A) = 3 - 2 = 1
N(A)=span{[12−1]}N(A) = \text{span}\bigg\{\begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix}\bigg\}
b∉range(A)b \notin \text{range}(A)

Therefore, there is no exact solution. We need to find the best approximation of bb in range(A)\text{range}(A).

B=[111331]B = \begin{bmatrix} 1 & 1 \\ 1 & 3 \\ 3 & 1 \end{bmatrix}
P=B(BTB)−1BTP = B(B^TB)^{-1}B^T
P=[111331][117711]−1[113131]P = \begin{bmatrix} 1 & 1 \\ 1 & 3 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 11 & 7 \\ 7 & 11 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 3 \\ 1 & 3 & 1 \end{bmatrix}
P=172[111331][11−7−711][113131]P = \frac{1}{72} \begin{bmatrix} 1 & 1 \\ 1 & 3 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 11 & -7 \\ -7 & 11 \end{bmatrix} \begin{bmatrix} 1 & 1 & 3 \\ 1 & 3 & 1 \end{bmatrix}
P=172[111331][4−1026426−10]P = \frac{1}{72} \begin{bmatrix} 1 & 1 \\ 1 & 3 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 4 & -10 & 26 \\ 4 & 26 & -10 \end{bmatrix}
P=172[816161668−416−468]P = \frac{1}{72} \begin{bmatrix} 8 & 16 & 16 \\ 16 & 68 & -4 \\ 16 & -4 & 68 \end{bmatrix}
Pb=172[816161668−416−468][12−1]=[1/313/6−5/6]Pb = \frac{1}{72} \begin{bmatrix} 8 & 16 & 16 \\ 16 & 68 & -4 \\ 16 & -4 & 68 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix} = \begin{bmatrix} 1/3 \\ 13/6 \\ -5/6 \end{bmatrix}
b∗=Pb=[1/313/6−5/6]b^* = Pb = \begin{bmatrix} 1/3 \\ 13/6 \\ -5/6 \end{bmatrix}

Now, the problem has a solution. However for the uniqueness, we need to check if AA is full row rank. Since AA has linearly dependent rows, AA is not full row rank. Therefore, the solution is not unique, hence we need to find the minimum norm solution. For that, we need to project bb onto the null space perpendicular to AA.

Starting with any solution xx,

x=[x1x2x3]x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}
Let x1=0\text{Let } x_1 = 0
[111123321][0x2x3]=[1/313/6−5/6]\begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 3 & 2 & 1 \end{bmatrix} \begin{bmatrix} 0 \\x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 1/3 \\ 13/6 \\ -5/6 \end{bmatrix}
x2=−76 and x3=96x_2 = \frac{-7}{6} \text{ and } x_3 = \frac{9}{6}
x=[0−7/69/6]x = \begin{bmatrix} 0 \\ -7/6 \\ 9/6 \end{bmatrix}
Now, xmin is the projection of x onto the null space perpendicular to A.\text{Now, $x_{min}$ is the projection of $x$ onto the null space perpendicular to $A$.}
xmin=ProjN(A)⊥x=ProjR(A∗)xx_{min} = \text{Proj}_{N(A)^{\perp}}x = \text{Proj}_{\text{R}(A^*)}x
A∗=[113122131]A^* = \begin{bmatrix} 1 & 1 & 3 \\ 1 & 2 & 2 \\ 1 & 3 & 1 \end{bmatrix}
range(A∗)=span{[111],[123]}\text{range}(A^*) = \text{span}\bigg\{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}\bigg\}
Q=[111213]Q = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}
P=Q(Q∗Q)−1Q∗P = Q(Q^*Q)^{-1}Q^*
P=[111213][36614]−1[111123]P = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix}
P=16[52−1222−125]P = \frac{1}{6} \begin{bmatrix} 5 & 2 & -1 \\ 2 & 2 & 2 \\ -1 & 2 & 5 \end{bmatrix}
xmin=Px=16[52−1222−125][0−7/69/6]=[−25/364/3631/36]x_{min} = Px = \frac{1}{6} \begin{bmatrix} 5 & 2 & -1 \\ 2 & 2 & 2 \\ -1 & 2 & 5 \end{bmatrix} \begin{bmatrix} 0 \\ -7/6 \\ 9/6 \end{bmatrix} = \begin{bmatrix} -25/36 \\ 4/36 \\ 31/36 \end{bmatrix}

#EE501 - Linear Systems Theory at METU